package _mst;

import _object.TreeNode;

import java.util.*;

/**
 * 面试题 04.09. 二叉搜索树序列
 */
public class T0409 {
    private List<List<Integer>> result;
    private LinkedList<Integer> path;
    private Deque<TreeNode> deque;

    public List<List<Integer>> BSTSequences(TreeNode root) {
        result = new LinkedList<>();
        path = new LinkedList<>();
        deque = new LinkedList<>();
        if (root != null) deque.offer(root);
        dfs();
        return result;
    }

    public void dfs() {
        if (deque.isEmpty()) {
            result.add(new ArrayList<>(path));
            return;
        }

        // 当前层可与选择的候选节点的个数
        for (int i = 0; i < deque.size(); i++) {
            TreeNode cur = deque.pollFirst();
            // 向路径中添加当前值
            path.add(cur.val);
            // 向候选队列中添加子节点
            if (cur.left != null) deque.offerLast(cur.left);
            if (cur.right != null) deque.offerLast(cur.right);

            // 递归
            dfs();

            // 回溯候选队列
            if (cur.left != null) deque.pollLast();
            if (cur.right != null) deque.pollLast();

            deque.offerLast(cur);

            // 回溯路径
            path.removeLast();
        }
    }
}
